package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/reorder-list/'>重排链表(Reorder List)</a>
 * <p>给定一个单链表 L 的头节点 head ，单链表 L 表示为：L0 → L1 → … → Ln - 1 → Ln</p>
 * <p>请将其重新排列后变为：L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …</p>
 * <p>不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：head = [1,2,3,4]
 *              1 -> 2 -> 3 -> 4 -> NULL
 *      输出：[1,4,2,3]
 *              1 -> 4 -> 2 -> 3 -> NULL
 *
 *  示例 2：
 *      输入：head = [1,2,3,4,5]
 *              1 -> 2 -> 3 -> 4 -> 5 -> NULL
 *      输出：[1,5,2,4,3]
 *              1 -> 5 -> 2 -> 4 -> 3 -> NULL
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>链表的长度范围为 [1, 5 * 10^4]</li>
 *     <li>1 <= node.val <= 1000</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/24 15:35
 */
public class LC0143ReorderList_M {
    static class Solution {
        public void reorderList(ListNode head) {
            //
            // 1.找到链表的中间
            ListNode slow = head;
            ListNode fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            // 此时slow为中点的前一个
            ListNode list2 = slow.next;
            slow.next = null;   // 断开
            // 2.反转后半段链表
            ListNode prevNode = null;
            ListNode nextNode;
            while (list2 != null) {
                nextNode = list2.next;
                list2.next = prevNode;
                prevNode = list2;
                list2 = nextNode;
            }
            list2 = prevNode;
            // 3.合并两段链表
            ListNode list1 = head;
            ListNode l1Temp;
            ListNode l2Temp;
            while (list1 != null && list2 != null) {
                l1Temp = list1.next;
                l2Temp = list2.next;
                list1.next = list2;
                list1 = l1Temp;
                list2.next = list1;
                list2 = l2Temp;
            }
        }
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);

        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(2);
        head2.next.next = new ListNode(3);
        head2.next.next.next = new ListNode(4);
        head2.next.next.next.next = new ListNode(5);

        Solution solution = new Solution();
        solution.reorderList(head1);
        Printer.printListNode(head1);
        solution.reorderList(head2);
        Printer.printListNode(head2);
    }
}
